• 先簡單回顧一下，今天預計分析的題目：

題目連結：https://leetcode.com/problems/merge-two-sorted-lists/

題目敘述：

• 題目有兩個已經排序好的 linked list，你要將這兩個 linked list 合併成一個已排序過的 linked list
  

測資的 Input/Output：

• 會拿到兩個 linked list，需要合併後回傳
  

• 這一題可以使用遞迴或迭代的方法實作，我們接下來會依序介紹

  • 遞迴方法：將大問題分解成小問題
    • 大問題：兩個 linked list 要排序
    • 分解成，每次只比對2個 linked list的數字，從這兩個數字找出比較小的，剩下的數字交給下一個 function 決定
    • 以 input l1 = [1,4] 跟 l2 = [2] 為例
      • [1, 4] 和 [2] 的合併結果 = 先比較 1 與 2，得到比較小的 1 (會得到 [1])，然後加上剩下的 [4] 與 [2] 的合併結果
      • [4] 和 [2] 的合併結果 = 先比較 4 與 2，得到比較小的 2 (會得到[2])，然後加上剩下的 [4] 與 [] 的合併結果
      • [4] 和 [] 的合併結果 = 由於 l2 為空，直接得到 l1 的 [4]
    • 所以整個程式邏輯
      1. 先判斷 l1 或 l2 是不是為空，若 l1 空了，那就 return l2，反之亦然 (終止條件) (注意，終止條件要先寫，避免程式永遠停不下來)
      2. 會一個一個比較 l1 與 l2 的值
         1. 若 l1 比較小，那這個值會留下來，然後將 l1 下一個數字 與 l2 數字為參數，再呼叫一次自身函數 (再執行一次 步驟1與2)
         2. 若 l2 比較小，那這個值會留下來，然後將 l1 與 l2 下一個數字為參數，再呼叫一次自身函數 (再執行一次 步驟1與2)
            

  class Solution:            
      def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
  #       若 l1 為空，就沒必要比較，直接回傳 l2，反之亦然
          if l1 == None: 
              return l2;
          if l2 == None: 
              return l1;
  
  #       判斷 input 的 l1 與 l2 第一個值誰比較大   (隨著每次呼叫自己，l1與l2會越來越短)
          if l1.val < l2.val: 
  #           l1 比較小，所以 l1 第一個值留下來，把 l1.next (第二個)值 跟 l2 再執行一次自身 function
              l1.next = self.mergeTwoLists(l1.next, l2);
  #           此時 return 的 l1 會是整串的，會包含 與 l2 相比，vl 這個比較小的值(第一個值)，還有 self.mergeTwoLists(l1.next, l2) 後的結果
              return l1;
  
          else:
              l2.next = self.mergeTwoLists(l1, l2.next);
              return l2;
  

  • 迭代方法：
    1. 先創立一個叫 merge 的空 Linked list (排序過後的內容，都會儲存在此)
    2. 使用迴圈的方式，一個一個比較 l1 與 l2 的值，直到 l1 或 l2 其中一個為空
       1. 若 l1 比較小，就讓 merge 接上當前 l1 的節點
       2. 若 l2 比較小，就讓 merge 接上當前 l2 的節點
    3. 若 l2 空了，那就會將剩餘的 l1 整串資料，接到 merge 尾端，反之亦然

class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
#       產生一個 ListNode 型態的 linked list，並且 val 裡面塞 None  (next 預設為 None)
        merge = ListNode(None)
#       用一個 pointer 指向 linked list尾端，隨著不斷 merge，將永遠指向 merge linked list 尾端來新增 node
        cursor = merge
#       若 l1 跟 l2 都不為空，則進行比較
        while l1 and l2:
#           比較 l1 跟 l2 的第一個元素 val，比較小的則加入 cursor 中，並將 後面的 linked list 覆蓋上原 linked list (所以比較小的數字會消失)
            if l1.val <= l2.val:
                cursor.next = l1
                l1 = l1.next
            elif l1.val > l2.val:
                cursor.next = l2
                l2 = l2.next
            cursor = cursor.next
#       若 l2 空了，則將剩下的 l1 全部接到尾端，反之亦然
        if l1:
            cursor.next = l1
        else:
            cursor.next = l2

        return merge.next

• 因為效率因素，所以此題大多數都是使用迭代方式解決